#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // ysh's method,pass 113/143
    //  bool canPartition(vector<int> &nums)
    //  {
    //      sort(nums.begin(), nums.end());
    //      int sum = accumulate(nums.begin(), nums.end(), 0);
    //      if (sum % 2 != 0)
    //      {
    //          return false;
    //      }
    //      int length = nums.size();
    //      if (length == 1)
    //      {
    //          return false;
    //      }
    //      int bag_weight = length;
    //      vector<int> nums_weight(length, 1);
    //      vector<int> dp(length + 1, 0);
    //      for (int i = 0; i < length; i++)
    //      {
    //          for (int j = bag_weight; j >= nums_weight[i]; j--)
    //          {
    //              dp[j] = max(dp[j], dp[j - nums_weight[i]] + nums[i]);
    //              if (dp[j] == sum / 2)
    //              {
    //                  return true;
    //              }
    //          }
    //      }
    //      return false;
    //  }

    // recall
    // bool backtracking(vector<int> &nums, vector<bool> &used, int res)
    // {
    //     if (sum == res)
    //     {
    //         return true;
    //     }
    //     if (sum > res)
    //     {
    //         return false;
    //     }
    //     for (size_t i = 0; i < nums.size(); i++)
    //     {
    //         if (used[i] == true)
    //         {
    //             continue;
    //         }
    //         sum += nums[i];
    //         used[i] = true;
    //         if (backtracking(nums, used, res))
    //         {
    //             return true;
    //         }
    //         used[i] = false;
    //         sum -= nums[i];
    //     }
    //     return false;
    // }
    // bool canPartition(vector<int> &nums)
    // {
    //     sum = 0;
    //     int num_sum = accumulate(nums.begin(), nums.end(), 0);
    //     if (nums.size() == 1 || num_sum % 2 != 0)
    //     {
    //         return false;
    //     }
    //     vector<bool> used(nums.size(), false);
    //     return backtracking(nums, used, num_sum / 2);
    // }
    // int sum;

    // book's method
    bool canPartition(vector<int> &nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0)
        {
            return false;
        }
        int target = sum / 2;
        vector<int> dp(target + 1, 0);
        for (int i = 0; i < (int)nums.size(); i++)
        {
            for (int j = target; j >= nums[i]; j--)
            {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if (dp[target] == target)
        {
            return true;
        }
        return false;
    }
};

int main()
{
    vector<int> nums{1, 2, 3, 5};
    Solution sol;
    cout << sol.canPartition(nums) << endl;
    return 0;
}
